import sys

#
# Below are variations of Minimax algorithm
#
def minimax(node, depth):
    if node.is_leaf():
        return node.value

    maxvalue = -sys.maxint
    for child in node.children:
        maxvalue = max(maxvalue, -minimax(child, depth-1))
    return maxvalue
        

def alphabeta(node, depth, alpha, beta):
    if node.is_leaf():
        return node.value
    
    for child in node.children:    
        alpha = max(alpha, -alphabeta(child, depth-1, -beta, -alpha))
        if beta <= alpha:
         break
    return alpha

def negascout(node, depth, alpha, beta):
    if node.is_leaf():
        return node.value
    a = alpha    
    b = beta
    for child in node.children:
        a = -negascout(child, depth-1, -b, -a)
        if a > alpha:
            alpha = a
        if alpha >= beta:
            return alpha
        if alpha >= b:
            alpha = -negascout(child, depth-1, -beta, -alpha)
            if alpha >= beta:
                return alpha
    return alpha        